The invention is particularly advantageously applicable in the field of radiofrequency identification, or “RFID”.
Radiofrequency identification is a technique for storing and recovering data remotely by using markers called radiofrequency identification tags (or “RFID tags”). A radiofrequency identification tag is a small object, such as a self-adhesive label, which can be glued to, or incorporated in, objects or products. It comprises an antenna associated with an electronic chip which enables it to receive and respond to radiofrequency requests sent from a transmitter-receiver called a reader. Radiofrequency identification tags are, for example, used to identify people when the tags are incorporated in passports, in transport tickets or in payment cards, or to identify products, as with a barcode.
Conventionally, the reader sends a particular interrogation signal over a radio channel, to which the tag responds. One possible response from the tag is a numerical identification of this tag. The reader can then look up a database to identify, or check access for the tag. With a view to protecting private life, notably the private life of people holding radiofrequency identification tags, it is generally desirable for the radiofrequency identification tag authentication protocol by a reader to have three properties:                the protocol must be anonymous, that is to say that it must not be possible for a malicious adversary to identify a tag used in an authentication.        the tag must not be traceable, that is to say that it must not be possible to link two different authentications of one and the same tag, and        if the malicious adversary obtains the identifier of a tag by any method whatsoever: by a so-called “reverse engineering” method, by a physical attack on the card, etc., it must not be possible to recognize former authentications of the tag. This last property is called the “forward privacy” property.        
When such a protocol is used to identify people, it will be understood that these three properties help to enable private life to be respected.
A protocol, called “OSK” protocol, has been proposed by Ohkubo, Suzuki and Kinoshita, which provides these three security properties. The protocol can be described as follows: a tag has a unique identifier, denoted ID, and a reader suitable for reading the tag has access to a database containing all the tag identifiers. On receiving an authentication request sent by the reader, the tag responds by sending a hash of its identifier, calculated from a first hash function, for example “SHA-256” (for “Secure Hash Algorithm”). We will denote this hash H1(ID).
Then, the tag updates its identifier ID by calculating a second hash of its identifier, denoted H2(ID), by using a second hash function H2, different from the first function. The new identifier ID is then H2(ID).
On receiving the first hash of the identifier H1(ID), the reader calculates the hash of the identifiers in the database by using the first hash function. If it finds a value equal to H1(ID), then the reader accepts the authentication of the tag and updates the identifier ID in the same way as the tag: by calculating H2(ID). If the reader does not find any value equal to H1(ID) in the database of identifiers, then the reader calculates the hash of all the identifiers by using the second hash function H2 and then it repeats the operation with the newly calculated identifiers until the authentication succeeds.
It is found that, with this protocol:                what circulates between the tag and the reader is a value obtained by applying a hash function to an identifier. A hash function, here denoted H, has the property that, for any x of which the image H(x) is known by the hash function, it is then very difficult to calculate y such that H(x)=H(y). By virtue of this property, the anonymity of the tag is respected. A malicious adversary who recovers the hash of the identifier cannot a priori retrieve the identifier;        each message sent by the tag in response to an authentication request corresponds to a different identifier since the identifier of a tag is updated between two authentications. The non-traceability property is therefore observed; and        since the identifier of a tag is updated between two authentication requests and the hash function is deemed nonreversible, then the malicious adversary who would recover a tag identifier would not be able to associate previous authentications with this tag identifier. Thus, the so-called “forward secrecy” property is observed.        
However, this authentication protocol has a few weaknesses. In practice, since the tag updates its identifier after each authentication request from the reader, the adversary who would make m successive authentication requests to the tag would provoke m updates by the tag of its identifier and a significant loss of sync between the tag and the reader. Thus, in a real authentication requested by the reader, the latter will update m times all the identifiers in the database of identifiers before finding the identifier that corresponds to the tag currently being authenticated. The m updates correspond to a resynchronization of the reader with the tag. Such an attack, of the denial of service type, has the aim of slowing down, or even saturating, such a radiofrequency identification system to ultimately prevent other authentications.
When the number of tags generated by the radiofrequency identification system is high, then the authentication of a tag becomes costly, in both time and resources. This example of attack, which is easy to conduct, makes an authentication protocol in a radiofrequency identification system ineffective. In a case, for example, in which such a system is located in public transport to enable subscribers to access said transport after being authenticated at an access terminal embodied by a turnstile, by presenting their subscription card containing a radiofrequency identification tag, the discontent of these subscribers is imagined if they have to wait a few seconds for the turnstile to open after having presented their subscription card, notably at peak times.
There is therefore a need for an authentication protocol in a radiofrequency identification system that is not sensitive to denial of service type attacks that tend to render the radiofrequency identification system ineffective.